Self-clocking glyph codes have been developed for embedding machine readable digital data in images of various descriptions. See, for example, a commonly assigned Bloomberg et al. United States continuing patent application, which was filed May 10, 1994 under Ser. No. 08/240,798 on "Self-Clocking Glyph Codes" (D/89194). Also see a commonly assigned Hecht et al. U.S. Pat. No. 5,453,605 which issued Sep. 26, 1995 on "Global Addressability for Self-Clocking Glyph Codes". To integrate these glyph codes into line art images, the data typically are embedded in small, similarly sized, spatially formatted, elliptical or slash-like marks or "glyphs" which are slanted to the left or right in generally orthogonal orientations to encode binary zeros ("0's") or ones ("1's"), respectively. Customarily, these glyphs are written on a spatially periodic, two-dimensional lattice of centers at a density that enables up to about 500 bytes of data per square inch to be stored on, say, a plain paper document. Clearly, therefore, these glyph codes are well suited for incorporating digital data channels into textual and other types of line art images. Indeed, one of the advantages of glyph codes of the foregoing type is that they tend to be esthetically unobtrusive because they have a generally uniform textured appearance and may sometimes even be perceived as having a substantially homogeneous gray scale appearance.
Tow described the use of "circularly asymmetric" halftone dots for incorporating self-clocking glyph codes into halftone images in a commonly assigned U.S. Pat. No. 5,315,098, which issued May 24, 1994 on "Methods and Means for Embedding Machine Readable Digital Data in Halftone Images." This is a workable approach if the data is confined to the midtone regions of the image in accordance with a known or identifiable spatial formatting rule. Unfortunately, however, excessive sensitivity is required to recover the embedded data with acceptable reliability from the darker or lighter regions of the image. Another drawback is that the background noise in halftone images that are composed of these asymmetric halftone dots may detract from the perceived quality of those images. For instance, four asymmetric dots may form a pattern extending radially outward from a central point, or they could form the sides of a square. These rotationally dependent differences are readily observable in images, and cause unwanted graininess and noise when viewing it.
My commonly assigned U.S. Pat. No. 5,706,099, which issued Jan. 6, 1998 on "Method and Apparatus for Generating Serpentine Halftone Images" and which is hereby incorporated by reference, provides a partial solution to the above problem by introducing circular serpentine halftone cell structures for embedding data in images. As shown in FIG. 1, these serpentine halftone cells have a high degree of rotational tone invariance. In practice, the circular arcs of these halftone cells vary in thickness as the cells vary in tone. Regardless of the tone, however, the central axis of each of the arcs of each of the halftone cells intersects adjacent sides of the cell at their respective midpoints. Thus, even though the embedded data value may cause the data axis (i.e., the axis of symmetry) of a cell to be oriented at +45.degree. or -45.degree. relative to the slow scan direction, the axes of these arcs substantially coincide with axes of the arcs of any adjacent halftone cells. See FIG. 1. Because the shape of the halftone cells at the cell boundary is similar regardless of the cell rotation, the noise associated with rotation is greatly reduced. These types of structures, with quarter circles in opposite corners of a square, are also known as Truchet tiles.
My above referenced patent further teaches that the arcuate fill patterns may be rotated 45.degree. with respect to the halftone cell boundaries to produce another rotationally distinguishable pair of halftone structures. These structures have been called Manhattans and also are sometimes referred to as ortho-serpentines. However, these Manhattan or ortho-serpentine structures have a greater rotational tone variance than the serpentine cell structures. Therefore, they are intended primarily for special purposes, such as to provide the additional rotationally distinguishable cell structures that are needed to embed a pair of data bits in each halftone cell.
Unfortunately, the circular arc pairs of the halftone cell structures described in my above patent impose unwanted constraints on the dynamic tone range over which embedded machine readable data can be effectively recovered from halftone images composed of such cell structures. Referring to FIG. 2, as the line weight or thickness of the arcs increase to produce darker tones, the arcs reach an overlap state, as at 15, and the extent of the overlap then increases as the tone darkens. Once this overlap occurs, there is only the shape information in the four corners of the cell to differentiate an embedded zero ("0") from an embedded one ("1"), with the attendant risk the shape information will be misinterpreted, especially as the amount of overlap increases. Clearly, therefore, it would be beneficial to have a technique for constructing half tone cells which not only have substantial rotational tone invariance, but which also provide a readily identifiable orientation indicia over an extended tone range.